#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.


"""
kahn 拓扑排序算法: 寻找是否有环

    # start : [1, 1, 2, 3]      1--->2 , 1--->3, 2--->3, 3---->1
    # end   : [2, 3, 3, 1]

关联题目: q127-topological-sorting.py
"""

from collections import defaultdict


class Solution:

    def isCyclicGraph(self, start, end):
        # start = [1, 2, 3], end = [2, 3, 1]
        # return self.is_cyclic_graph_by_topological(start, end)
        return self.dfs_check(start, end)

    # =================== dfs to find has cycle in directed graph =====================
    def dfs_check(self, start_nodes, end_nodes):
        # 实质上是一个 tarjan算法
        # 用一个stack表示当前正在访问中的元素, 一个visited或者non_visited确定节点是否已经被淘汰(判断横边)

        self.nodes = defaultdict(list)
        self.build_adjacent_list(start_nodes, end_nodes)

        # self.visit_stack = []
        self.stack_set = set()      # 这里用set代替stack是可以的(因为没有用到栈的pop功能)
        self.non_visited = set(self.nodes)

        # 1: 如果节点没有后继, 或者全部访问完毕, 出栈.
        # 2: 如果后继节点在栈中(后集节点一定在visited中, 这次访问是一条返祖边), 那么存在环.
        # 3: 如果后继节点在visited中(可以换成non_visited), 但不在栈中(横边, 不用处理)
        while self.non_visited:
            # 注意: 也要能处理自己到自己的回路(比如 1--> 1)
            node = self.non_visited.pop()
            exist_cycle = self.exist_cycle_dfs_travel(node)

            # print('=================== after loop %s' % self.non_visited)
            # print('exist %s' % exist_cycle)
            if exist_cycle:
                return True

        return False

    def build_adjacent_list(self, starts, ends):
        for src, dst in zip(starts, ends):
            self.nodes[src].append(dst)

    def exist_cycle_dfs_travel(self, node):
        # self.visit_stack.append(node)
        self.stack_set.add(node)

        for child in self.nodes[node]:
            if child not in self.non_visited:
                # if child in self.visit_stack:
                # NOTE: 表示child还在栈中没有处理完, 然后兜兜转转又访问到了这个child(存在环)
                if child in self.stack_set:
                    return True
                else:
                    continue

            self.non_visited.remove(child)
            exist_cycle = self.exist_cycle_dfs_travel(child)
            if exist_cycle:
                return True

        # v = self.visit_stack.pop()
        v = self.stack_set.remove(node)

        # assert v is node
        return False

    # =================== topological sort to check exist cycle in directed graph =====================
    def is_cyclic_graph_by_topological(self, start, end):
        if not start:
            return False

        self.start, self.end = start, end
        self.edge_num = len(start)
        self.nodes = defaultdict(list)    # {node_value : [neighbors]} 节点和后继节点
        self.in_degree = defaultdict(int) # {node_value : [in_degree]} 节点indegree

        self.build_neighbors_and_degree()
        self.zero_degree_nodes = self.find_zero_in_degree()
        # self.topological_list = []
        # self.ready_to_handles = set(self.nodes)

        while self.zero_degree_nodes:
            zero_in_node = self.zero_degree_nodes.pop()          # 0入度元素, 即没有前驱元素(类似于根节点)
            # self.topological_list.append(zero_in_node)         # 拓扑排序列表构建
            # self.ready_to_handles.remove(zero_in_node)         # 循环完毕后: 剩下的待处理节点就是环中的节点

            for nei in self.nodes[zero_in_node]:
                self.in_degree[nei] -= 1
                self.edge_num -= 1

                if self.in_degree[nei] == 0:
                    self.zero_degree_nodes.append(nei)

        # print(self.ready_to_handles)                             # 环中的节点
        # 最后剩下了入度不为0的元素没有处理
        # return bool(self.ready_to_handles)
        return self.edge_num != 0

    def build_neighbors_and_degree(self):
        for source, dest in zip(self.start, self.end):
            # NOTE: 访问source和dest, 使得self.nodes和self.in_degree中一定存在这些节点: 比如输入start=[1], end=[2]
            self.nodes[source]
            self.nodes[dest]
            self.in_degree[source]
            self.in_degree[dest]

            self.nodes[source].append(dest)
            self.in_degree[dest] += 1

    def find_zero_in_degree(self):
        result = []
        for node, degree in self.in_degree.items():
            if degree == 0:
                result.append(node)

        return result

def main():
    print("start main")
    s = Solution()
    # ret = s.isCyclicGraph([1], [2])
    ret = s.isCyclicGraph([1, 2], [2, 3])
    # ret = s.isCyclicGraph([1, 2], [2, 1])
    # ret = s.isCyclicGraph([1, 2, 3], [2, 3, 2])
    print(ret)


if __name__ == "__main__":
    main()
